In a number of e-commerce applications, objects with multiple attributes need to be classified, using a given set of rules, as efficiently as possible. For example, an HTTP request may be classified based on the source-address, destination-address, host server, and the name of the file it requests. An e-commerce application may want to give priority to all HTTP service requests from Company ‘X’ to Company ‘Y’ that request global sales-updates. An IP packet may be classified based on its five-tuple.
Previously, attention was focused toward packet classification in the context of internet routers. This deals with the fast classification of IP packets based on values of the 5-tuple (source address, destination address, source port, destination port, and protocol) in the IP packet header. These methods exploit properties of IP routes, semantics of the actual databases of rules, and properties of specific hardware implementations to expedite the classification. They also use certain efficient data structures to store classification rules and fasten computations. These methods however do not deal with the problem of objects whose attributes lie in a arbitrarily large dimension. These algorithms also presumes availability/capability of tailored hardware solutions. Thus, these algorithms are limited in that they work in limited number of dimensions; do a limited classification; exploit properties of hardware; and do not consider that different rules could imply different cost etc.